package com.platform.modules.alg.alglib.poj2019;

public class Poj2019 {
    public String output = "";

    private final int maxn = 260;

    int a[][] = new int[maxn][maxn];
    int lb[] = new int[maxn];
    int Fmax[][][] = new int[maxn][maxn][11];
    int Fmin[][][] = new int[maxn][maxn][11];

    // 求解所有 log 值,保存到数组 lb[]
    void Initlog() {
        lb[0] = -1;
        for (int i = 1; i < maxn; i++)
            lb[i] = (i & (i - 1)) > 0 ? lb[i - 1] : lb[i - 1] + 1;
    }

    void ST(int n) {
        for (int k = 1; k <= n; k++) // 多一维
            for (int i = 1; i <= n; i++)
                Fmax[k][i][0] = Fmin[k][i][0] = a[k][i];
        for (int k = 1; k <= n; k++)
            for (int j = 1; j <= lb[n]; j++)
                for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                    Fmax[k][i][j] = Math.max(Fmax[k][i][j - 1], Fmax[k][i + (1 << (j - 1))][j - 1]);
                    Fmin[k][i][j] = Math.min(Fmin[k][i][j - 1], Fmin[k][i + (1 << (j - 1))][j - 1]);
                }
    }

    // 从坐标为(x,y)的地方开始，右下扩展 B 长度
    void solve(int x, int y, int B) {
        int k = lb[B];
        int maxx = -1;
        int minx = 0x3f3f3f3f;
        int l = y, r = y + B - 1;
        for (int i = x; i < x + B; i++) { // 查询每一行的最值
            maxx = Math.max(maxx, Math.max(Fmax[i][l][k], Fmax[i][r - (1 << k) + 1][k]));
            minx = Math.min(minx, Math.min(Fmin[i][l][k], Fmin[i][r - (1 << k) + 1][k]));
        }
        output += (maxx - minx) + "\n";
    }

    public String cal(String input) {
        int N, B, K;
        int x, y; // 每次查询的坐标
        Initlog();
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        N = Integer.parseInt(words[0]);
        B = Integer.parseInt(words[1]);
        K = Integer.parseInt(words[2]);

        for (int i = 1; i <= N; i++){
            String[] nums = line[i].split(" ");
            for (int j = 1; j <= N; j++){
                a[i][j] = Integer.parseInt(nums[j-1]);
            }

        }
        ST(N);
        for (int i = 0; i < K; i++) {
            String[] query = line[1 + N+i].split(" ");
            x = Integer.parseInt(query[0]);
            y = Integer.parseInt(query[1]);
            solve(x, y, B);
        }
        return output;
    }
}
